The present invention relates to route determination in a vehicle navigation system. More specifically, the present invention determination of alternate routes, i.e., detours, when road conditions make an originally determined route undesirable or impassable.
Because updating map databases with up-to-the-minute information regarding road conditions is an exceedingly challenging task (even for so-called intelligent vehicle/highway systems), currently available vehicle navigation systems often determine routes on which the user may encounter unforeseen or unforeseeable obstacles such as, for example, road construction or excessive traffic. In such situations it is desirable for the navigation system to have the capability to determine an alternate route "on the fly" to avoid the obstacle.
Some systems rely on user input to the route determination algorithms to determine routes which are most likely to be the easiest and fastest, i.e., the optimum route. By prospectively selecting appropriate route determination criteria, the user can use her knowledge of actual road conditions to facilitate determination of the best available route. For example, the user may specify that the system make maximum use of freeways, or, alternatively, that no freeways be used at all. The user may also specify that the route have a minimum number of turns, or that it be the shortest distance between the source and the destination. In addition, the user may specify that the route avoid all known obstacles such as, for example, toll booths. Unfortunately, while this approach provides some flexibility, it cannot anticipate and correct for road obstacles for which the user has little or no warning.
One approach to "on the fly" obstacle avoidance allows the user to tell the system to prohibit an upcoming maneuver in response to which the system determines a short detour from the point of the prohibited maneuver back to some subsequent point on the original route. This may be understood with reference to FIG. 1. As the user is proceeding east on road 102 along original route 104, she notices that road 106 is closed to the right because of construction. As a result, the right turn maneuver suggested by the system has become impossible. By refusing the indicated maneuver with the user interface, the user alerts the system to the obstacle. The system then determines an alternate route 108 based on the assumption that the right turn maneuver from road 102 to road 106 is not allowed. This results in the detour via roads 110 and 112 which leads back to road 106 as soon as possible.
Unfortunately, the above-described approach is problematic where, for example, the entire portion of road 106 between roads 102 and 114 is closed. Such a situation is addressed by another approach which will be described with reference to FIG. 2. As in the previous example, the user alerts the system to the fact that the right turn maneuver onto road 106 is not possible. However, according to this approach, the system avoids the portion of road 106 between the two successive maneuvers at the intersection of roads 102 and 106 (i.e., the right turn mentioned above), and the intersection of roads 106 and 114 (a left turn). By ignoring the road segments between the next two upcoming maneuvers, an alternate route 202 is determined which avoids the problem discussed above.
However, despite the apparent advantages offered by each of these approaches, none allows the user to contribute input as to the nature of the alternate route based on her perception of the road conditions. Thus, none of the above-described approaches is sufficient to adapt to the high degree of variability of road conditions which may be encountered by the user. A more flexible approach to "on the fly" determination of alternate routes is therefore desirable.